package com.company;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by asus on 2018/7/4.
 */
public class DynamicPlanning {
    public static void main(String[] args) {
        int[][] cell = new int[4][4];
        Map<Integer, Integer> weightMap = new HashMap<>();
        Map<Integer, Integer> priceMap = new HashMap<>();
        weightMap.put(0,1);
        weightMap.put(1,4);
        weightMap.put(2,3);
        weightMap.put(3,1);
        priceMap.put(0,1500);
        priceMap.put(1,3000);
        priceMap.put(2,2000);
        priceMap.put(3,2000);
        for (int i = 0; i < 4; i++){
            for (int j = 0; j < 4; j++){
                Integer last = 0;
                Integer now = 0;
                if (i - 1 >= 0){
                    last = cell[i-1][j];
                }
                if (j + 1 >= weightMap.get(i)){
                    now = now + priceMap.get(i);
                }
                if (i - 1 >= 0 && j - weightMap.get(i) >= 0){
                    now = now + cell[i-1][j - weightMap.get(i)];
                }
                cell[i][j] = last > now ? last : now;
            }
        }
        System.out.println(cell[3][3]);
    }
}
